public class KMPMatcher {

    public static void main(String[] args) {
//        String text = "aaaaaaag";
//        String pattern = "aaaag";
//
//        int matchPosition = kmpMatch(text, pattern);
//
//        if (matchPosition != -1) {
//            System.out.println("Substring found at index: " + matchPosition);
//        } else {
//            System.out.println("Substring not found.");
//        }

        System.out.println('u' - 'h');
    }

    private static int kmpMatch(String text, String pattern) {
        int[] next = computeNextArray(pattern);
        int i = 0; // 文本串指针
        int j = 0; // 模式串指针

        for (int i1 : next) {
            System.out.println(i1);
        }
        while (i < text.length() && j < pattern.length()) {
            if (text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
                //ok
            } else {
                if (j > 0) {
                    j = next[j - 1];
                } else {
                    i++;
                }
            }
        }
        if (j == pattern.length()) {
            return i - j; // 匹配成功
        } else {
            return -1; // 匹配失败
        }
    }

    private static int[] computeNextArray(String pattern) {
        int[] next = new int[pattern.length()];
        int j = 0;
        for (int i = 1; i < pattern.length(); i++) {
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }
            if (pattern.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }

}